﻿#define _CRT_SECURE_NO_WARNINGS 1


#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution
{
public:
    int numberOfArithmeticSlices(vector<int>& nums)
    {
        int n = nums.size();
        // 优化
        unordered_map<long long, vector<int>> hash;

        for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);

        vector<vector<int>> dp(n, vector<int>(n)); // 创建 dp 表
        int sum = 0;

        for (int j = 2; j < n; j++) // 固定倒数第⼀个数
        {
            for (int i = 1; i < j; i++) // 枚举倒数第⼆个数
            {
                long long a = (long long)nums[i] * 2 - nums[j]; // 处理数据溢出
                if (hash.count(a))
                    for (auto k : hash[a])
                        if (k < i) dp[i][j] += dp[k][i] + 1;
                        else break;
                sum += dp[i][j];
            }
        }

        return sum;
    }
};

int main()
{
    vector<int> nums = { 2, 4, 6, 8, 10 };


    cout << Solution().numberOfArithmeticSlices(nums) << endl;

    return 0;
}


